//https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/description/?envType=daily-question&envId=2024-03-16


class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>>f(m, vector<int>(n, 0)); // ij表示走到i，j处的最长步数

        int res = 0;
        // 注意一定要这样遍历，因为我们初始化为dp为0，在更新时需要用到前1列的数据
        for(int j = 1; j < n; j ++)
            for(int i = 0; i < m; i ++){
                // i j可以从 [i - 1][j - 1], [i][j - 1], [i + 1][j - 1]转移过来 
                for(int k = max(0, i - 1); k < min(i + 2, m); k ++){
                    if(grid[k][j - 1] >= grid[i][j]) continue; // 不满足条件
                    if(j > 1 && f[k][j - 1] == 0) continue; // 这里是因为前面一格过不去
                    else{ 
                        f[i][j] = max(f[i][j], 1 + f[k][j - 1]);
                        //cout << i << " " << j << endl;
                    }
                }
                res = max(res, f[i][j]);
            }
        return res;
    }
};

